package com.example.leetcode.linked_list;

import java.util.ArrayList;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * 反向输出链表
 */
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> out = new ArrayList<Integer>();
        if (listNode == null) {
            return out;
        }
        Stack<Integer> stack = new Stack<Integer>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            out.add(stack.pop());
        }
        return out;
    }

  /*  public static void main(String[] args) {
        // {67,0,24,58}
        ListNode listNode1 = new ListNode(67);
        ListNode listNode2 = new ListNode(0);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(24);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(58);
        listNode3.next = listNode4;
        System.out.println(new Solution().printListFromTailToHead(listNode1));
    }*/


    /**
     * 输入一个链表，反转链表后，输出新链表的表头。
     *
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {
        if (head == null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        ListNode pre = null, next;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while (head != null) {
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }

/*  public static void main(String[] args) {
        // {67,0,24,58}
        ListNode listNode1 = new ListNode(67);
        ListNode listNode2 = new ListNode(0);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(24);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(58);
        listNode3.next = listNode4;

        ListNode reverse=  new Solution().ReverseList(listNode1);
        while (reverse!=null){
            System.out.println(reverse.val);
            reverse=reverse.next;
        }
    }*/

    /**
     * 链表中倒数第k个结点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) { //5,{1,2,3,4,5}
        ListNode p, q;
        p = q = head;
        int i = 0;
        for (; p != null; i++) {
            if (i >= k){
                q = q.next;
                System.out.println(q.val);
            }

            p = p.next;
        }
        return i < k ? null : q;
    }

    public static void main(String[] args) {
        // {67,0,24,58}
        ListNode listNode1 = new ListNode(67);
        ListNode listNode2 = new ListNode(0);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(24);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(58);
        listNode3.next = listNode4;

        ListNode find = new Solution().FindKthToTail(listNode1, 2);
        System.out.println(find.val);
    }

}